package leetcode.top100;

import org.junit.Test;

import java.util.Map;

/**
 * @author ：zsy
 * @date ：Created 2022/10/22 12:24 AM
 * @description：
 */
public class _005_最长回文子串 {
    @Test
    public void test() {
        System.out.println(new Solution().longestPalindrome("babad"));
    }

    class Solution {
        public String longestPalindrome(String s) {
            if (s.length() < 2) return s;
            int maxLen = 1;
            int begin = 0;
            char[] chars = s.toCharArray();
            for (int i = 0; i < chars.length - 1; i++) {
                // 以chars为偶数中心展开
                int evenLen = expendAroundCenter(chars, i, i);
                // 以chars为奇数中心展开
                int oddLen = expendAroundCenter(chars, i, i + 1);

                int curMaxLen = Math.max(evenLen, oddLen);

                if (curMaxLen > maxLen) {
                    maxLen = curMaxLen;
                    begin = i - (maxLen - 1) / 2;
                }
            }
            return s.substring(begin, begin + maxLen);
        }

        private int expendAroundCenter(char[] chars, int left, int right) {
            while (left >= 0 && right < chars.length && chars[left] == chars[right]) {
                left--;
                right++;
            }
            // len = right - left + 1 1- 2;
            return right - left - 1;
        }
    }


}
